// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的数字可以无限制重复被选取。
// 思路，回溯
// 该题的递归深度不固定，元素可以重复，所以单层遍历的时候不需要通过startIndex避免重复
function combinationSum(candidates, target) {
    let result = []
    let path = []
    function backtracking(startIndex, sum) {
        if (sum > target) {
            return
        }
        if (sum === target) {
            result.push([...path])
        }
        for (let i = startIndex; i < candidates.length; i++) {
            path.push(candidates[i])
            backtracking(i, sum + candidates[i])
            path.pop()            
        }
    }
    backtracking(0, 0)
    return result
}

let candidates = [2,3,5], target = 8
console.log(combinationSum(candidates, target))